package com.lun.swordtowardoffer2.c12;

import java.util.PriorityQueue;

import com.lun.util.SinglyLinkedList.ListNode;

public class MergeKList {

	//方法一：利用最小堆选取最小的节点
	public ListNode mergeKList(ListNode[] lists) {
		PriorityQueue<ListNode> minHeap = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
		ListNode fakeHead = new ListNode(-1);
		ListNode cur = fakeHead;
		
		for(ListNode list : lists) {
			minHeap.offer(list);
		}
		
		while(!minHeap.isEmpty()) {
			ListNode temp = minHeap.poll();
			cur.next = temp;
			cur = cur.next;
			
			if(temp.next != null) {
				minHeap.offer(temp.next);
			}
		}
		
		return fakeHead.next;
	}
	
	//方法二：按照归并排序的思路合并链表
	public ListNode mergeKList2(ListNode[] lists) {
		return mergeKList2(lists, 0, lists.length);
	}
	
	public ListNode mergeKList2(ListNode[] lists, int start, int end) {
		if(start + 1 == end) {
			return lists[start];
		}
		
		int mid = (start + end) / 2;
		ListNode head1 = mergeKList2(lists, start, mid);
		ListNode head2 = mergeKList2(lists, mid, end);
		
		return merge(head1, head2);
	}

	//方法三：两两合并
	public ListNode mergeKList3(ListNode[] lists) {
		ListNode cur = null;
		
		for(ListNode list : lists) {
			cur = merge(cur, list);
		}
		
		return cur;
	}
	
	private ListNode merge(ListNode head1, ListNode head2) {
		ListNode fakeHead = new ListNode(-1);
		ListNode cur = fakeHead;
		
		while(head1 != null && head2 != null) {
			if(head1.val < head2.val) {
				cur.next = head1;
				head1 = head1.next;
			}else {
				cur.next = head2;
				head2 = head2.next;
			}
			cur = cur.next;
		}
		
		cur.next = head1 == null ? head2 : head1;
		return fakeHead.next;
	}

}
